#ifndef LNKLS_H_
#define LNKLS_H_

#include "tools.hpp"
#include <cstddef>
#include <cstdio>
#include <string>
#include <type_traits>


namespace lxj
{
template<class T,
         std::enable_if_t<std::is_arithmetic_v<T> || std::is_same_v<T, std::string>, int> = 0>
struct Node {   // 表示单向链表时，只启用_right表示next指针
    T     _value;
    Node* _right;
    Node* _left;

    Node(T value = T{}) : _value(value), _right(nullptr), _left(nullptr) {}
    Node(const T& value, Node* right, Node* left) : _value(value), _right(right), _left(nullptr) {}
    ~Node() { _left = _right = nullptr; }
};

template<class T,
         std::enable_if_t<std::is_arithmetic_v<T> || std::is_same_v<T, std::string>, int> = 0>
struct NodeRand {   // 表示单向链表时，只启用_right表示next指针
    T         _value;
    NodeRand* _right;
    NodeRand* _random;   // 指向随机位置

    NodeRand(T value = T{}) : _value(value), _right(nullptr), _random(nullptr) {}
    NodeRand(const T& value, NodeRand* right, NodeRand* left)
        : _value(value), _right(right), _random(nullptr)
    {
    }
    ~NodeRand() { _random = _right = nullptr; }
};

// 构建链表
// 传入head为链表头结点的值，size为链表长度。除了头结点，其他节点随机生成
template<class T>
inline Node<T>* make_link(T head, size_t size)
{
    Node<T>* h = new Node<T>(head);
    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, std::string> &&
                  !std::is_same_v<T, char> && !std::is_same_v<T, bool>) {
        auto&    random = lxj::Random<T>::instance();
        Node<T>* cur    = h;
        while (--size) {
            cur->_right = new Node<T>(random(-100, 100));
            // cur->_right = new Node<T>(size);
            cur = cur->_right;
        }
    }
    else if constexpr (std::is_same_v<T, char> || std::is_same_v<T, bool>) {
        auto&           random  = lxj::Random<short>::instance();
        Node<T>*        cur     = h;
        constexpr short l_range = 0;
        constexpr short r_range = std::is_same_v<T, bool> ? 1 : 26;
        if (std::is_same_v<T, char>) {
            while (--size) {
                cur->_right = new Node<T>('a' + random(l_range, r_range));
                cur         = cur->_right;
            }
        }
        else {
            while (--size) {
                cur->_right = new Node<T>('0' + random(l_range, r_range));
                cur         = cur->_right;
            }
        }
    }
    else {
        auto&    random = lxj::Random<short>::instance();
        Node<T>* cur    = h;
        while (--size) {
            T value;
            value.reserve(4);
            for (short i = 0; i < 4; i++) {
                value.push_back('a' + random(0, 26));
            }
            cur->_right = new T(value);
            cur         = cur->_right;
        }
    }
    return h;
}

// 销毁链表
template<class T>
inline void destory_link(Node<T>* head)
{
    if (head == nullptr) return;
    unlock_link(head);
    while (head != nullptr) {
        auto cur = head;
        head     = head->_right;
        delete cur;
        cur = nullptr;
    }
}

template<class T>
inline void destory_link(NodeRand<T>* head)
{
    if (head == nullptr) return;
    while (head != nullptr) {
        auto cur = head;
        head     = head->_right;
        delete cur;
        cur = nullptr;
    }
}

// 使两个链表相交与较长链表的inter_pos处
// inter_pos大于最长链表的长度时，不做任何处理
template<class T>
inline void make_link_intersection(Node<T>* head_1, Node<T>* head_2, size_t inter_pos)
{
    if (head_1 == nullptr || head_2 == nullptr) return;
    size_t len1 = length(head_1);
    size_t len2 = length(head_2);
    if (inter_pos <= (len1 < len2 ? len1 : len2)) return;

    Node<T>* cur1 = len1 > len2 ? head_1 : head_2;
    Node<T>* cur2 = cur1 == head_1 ? head_2 : head_1;
    while (cur2->_right != nullptr) {
        cur2 = cur2->_right;
    }
    while (--inter_pos) {
        cur1 = cur1->_right;
    }
    cur2->_right = cur1;
}

// 打印链表的值
template<class T>
inline void print(Node<T>* head)
{
    if (head == nullptr) return;
    auto cur = head;
    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, char>) {
        while (cur != nullptr) {
            std::printf("%d, ", cur->_value);
            cur = cur->_right;
        }
    }
    else if constexpr (std::is_same_v<T, char> || std::is_same_v<T, bool>) {
        while (cur != nullptr) {
            std::printf("%c, ", cur->_value);
            cur = cur->_right;
        }
    }
    else {
        while (cur != nullptr) {
            std::printf("%4s, ", cur->_value.c_str());
            cur = cur->_right;
        }
    }
}

// 返回链表的长度
template<class T>
inline size_t length(Node<T>* head)
{
    size_t len = 0;
    for (auto p = head; p != nullptr; p = p->_right) {
        len++;
    }
    return len;
}

// 返回两个无环链表相交的第一个节点，无交点返回null
template<class T>
inline Node<T>* get_intersection_node(Node<T>* head_1, Node<T>* head_2)
{
    size_t len1 = length(head_1);
    size_t len2 = length(head_2);

    Node<T>* cur1 = len1 >= len2 ? head_1 : head_2;
    Node<T>* cur2 = cur1 == head_1 ? head_2 : head_1;
    for (size_t i = (len1 - len2) > 0 ? len1 - len2 : len2 - len1; i != 0; i--) {
        cur1 = cur1->_right;
    }

    while (cur1 != nullptr && cur1 != cur2) {
        cur1 = cur1->_right;
        cur2 = cur2->_right;
    }

    return cur1;
}

// 每k个节点一组，反转链表。
// k大于所给链表长度，不做处理
template<class T>
inline Node<T>* flip_link(Node<T>* head, size_t k)
{
    size_t len = length(head);
    if (len == 0 || len < k || k <= 1) return head;

    Node<T>*p1 = nullptr, *p2 = head, *p3 = head->_right;
    Node<T>*begin = nullptr, *end = head;
    size_t  end_pos = len - len % k;

    for (size_t i = 0; i < k; i++) {
        p2->_right = p1;
        p1         = p2;
        p2         = p3;
        p3         = p3 == nullptr ? p3 : p3->_right;
    }
    head = p1;
    end_pos -= k;
    begin       = p2;
    end->_right = begin;

    while (end_pos != 0) {
        for (size_t i = 0; i < k; i++) {
            p2->_right = p1;
            p1         = p2;
            p2         = p3;
            p3         = p3 == nullptr ? p3 : p3->_right;
        }
        end->_right   = p1;
        end           = begin;
        begin->_right = p2;
        begin         = p2;
        end_pos -= k;
    }

    return head;
}

// 复制带随机指针的链表
template<class T>
inline NodeRand<T>* copy_link(NodeRand<T>* head)
{
    if (head == nullptr) return nullptr;
    NodeRand<T>* h = new NodeRand<T>(head->_value);

    auto cur1 = head;
    auto cur2 = h;
    while (cur1 != nullptr) {
        cur2->_right = cur1->_right;
        cur1->_right = cur2;
        cur1         = cur2->_right;
        cur2         = cur1 == nullptr ? cur2 : new NodeRand<T>(cur1->_value);
    }

    cur1 = head;
    cur2 = cur1->_right;

    while (cur1 != nullptr) {
        if (cur1->_random == nullptr) {
            cur2->_random = nullptr;
        }
        else if (cur1->_random == cur1) {
            cur2->_random = cur2;
        }
        else {
            cur2->_random = cur1->_random->_right;
        }
        cur1 = cur2->_right;
        cur2 = cur1 == nullptr ? cur1 : cur1->_right;
    }

    cur1 = head;
    cur2 = h;

    while (cur1 != nullptr) {
        cur1->_right = cur2->_right;
        cur1         = cur1->_right;
        cur2->_right = cur1 == nullptr ? cur1 : cur1->_right;
        cur2         = cur2->_right;
    }
    return h;
}

// 力扣234--判断链表是否是回文结构
template<class T>
inline bool is_palindrome(Node<T>* head)
{
    if (head == nullptr || head->_right == nullptr) return true;
    Node<T>*cur = head, *next = head->_right, *p1 = nullptr, *p2 = head;
    while (p2 != nullptr && p2->_right != nullptr) {
        p2          = p2->_right->_right;
        cur->_right = p1;
        p1          = cur;
        cur         = next;
        next        = next->_right;
    }

    p2     = p2 == nullptr ? cur : next;
    next   = p1->_right;
    bool b = true;
    while (p1 != nullptr) {
        b &= (p1->_value == p2->_value) ? true : false;
        p2 = p2->_right;

        p1->_right = cur;
        cur        = p1;
        p1         = next;
        next       = next == nullptr ? next : next->_right;
    }

    return b;
}

// 返回一个链表的入环节点
template<class T>
inline Node<T>* link_ring_pos(Node<T>* head)
{
    if (head == nullptr || head->_right == nullptr || head->_right->_right == nullptr)
        return nullptr;

    Node<T>*p1 = head, *p2 = head;
    while (p2 != nullptr && p2->_right != nullptr) {
        p1 = p1->_right;
        p2 = p2->_right->_right;
        if (p1 == p2) break;
    }
    if (p2 == nullptr || p2->_right == nullptr) return nullptr;
    p2 = head;
    while (p1 != p2) {
        p1 = p1->_right;
        p2 = p2->_right;
    }

    return p1;
}

// 给链表解环
template<class T>
inline void unlock_link(Node<T>* head)
{
    Node<T>* cur = link_ring_pos(head);
    if (cur == nullptr) return;
    auto p = cur;
    while (p->_right != cur) {
        p = p->_right;
    }
    p->_right = nullptr;
}

// 力扣148 链表排序
template<class T>
inline Node<T>* sort_link(Node<T>* head)
{
    if (head == nullptr) return head;
    unlock_link(head);

    size_t   len      = length(head);
    Node<T>* new_head = head;
    for (int i = 1; i < len; i *= 2) {
        Node<T>* end1 = new_head, *p1 = end1;
        Node<T>* end2 = new_head, *p2 = end2;
        int      k   = 0;
        Node<T>* cur = nullptr;
        while (end2 != nullptr) {
            for (int j = 0; j < i; j++) {
                end1 = end1 == nullptr ? end1 : end1->_right;
            }
            p2   = end1;
            end2 = p2;
            for (int j = 0; j < i; j++) {
                end2 = end2 == nullptr ? end2 : end2->_right;
            }

            if (cur == nullptr) {
                cur = (p2 == nullptr || p1->_value <= p2->_value) ? p1 : p2;
            }
            else {
                cur->_right = (p2 == nullptr || p1->_value <= p2->_value) ? p1 : p2;
            }
            new_head = (k++ == 0) ? cur : new_head;
            while (p1 != end1 && p2 != end2) {
                Node<T>* min = p1->_value <= p2->_value ? p1 : p2;
                if (p1->_value <= p2->_value) {
                    p1          = p1->_right;
                    cur->_right = min;
                    cur         = cur->_right;
                }
                else {
                    p2          = p2->_right;
                    cur->_right = min;
                    cur         = cur->_right;
                }
            }
            if (p1 != end1) {
                cur->_right = p1;
                while (cur->_right != end1) cur = cur->_right;
                cur->_right = end2;
            }
            if (p2 != end2) {
                cur->_right = p2;
                while (cur->_right != end2) cur = cur->_right;
            }

            end1 = end2;
            p1   = end1;
        }
    }

    return new_head;
}

}   // namespace lxj

#endif